\subsubsection{pseudocodigo}

A continuación se presenta nuevamente el pseudocódigo 
mostrado en la seccion de demostracion de correctitud

\begin{quote}
\begin{verbatim}
Buscar()

    Tablero
    S[NxM] = <NxM,0,,,0>
    MejorSolucion = NxM
    i  = 1

    mientras i>= 0 
        si i == NxM
            O(1) - grabar solucion si es mejor que anteriores en MejorSolucion
            O(1) i = i-1 
            continue
        si S[i] = 0
            O(NxM - i-1) - buscar ficha en Q que encaje en el 
            tablero en la posicion i

            O(1) - S[i] = cantidad de opciones de fichas en Q para la pos i del tablero
            O(1) - i = i+1
            - continue 

        O(1) - S[i] =  S[i]- 1    
        Si S[i] = 0 
            O(1) - devolver la ficha en la posicion i a Q
        	O(1) i = i-1 
			continue

        si S[i] > 0            
            O(NxM - i - 1 ) - buscar ficha en Q que encaje en el tablero, devolviendo la que estaba en la
            posicion i
            O(1) - posicionar la ficha elegida en el tablero
            O(1) - i = i+1
            continue

    Return MejorSolucion
\end{verbatim}
\end{quote}
% \begin{quote}
% \begin{verbatim}

% Siendo K = NxM

% Buscar(i)
    
%     MejorSolucion = NxM
    
%     O(K) Para f entre las fichas de Q que encajan 
%     	 en el la posicion i 

%         O(1) Ubicar la ficha f en el tablero
%         //O(Buscar(K-1)) representa el orden de complejidad
%         //de mi algoritmo para una instancia de tamaño K
%         O(Buscar(K-1)) solucionActual = Buscar(i+1)
%         if solucionActual < MejorSolucion
%             MejorSolucion = solucionActual

%     Return MejorSolucion
% \end{verbatim}
% \end{quote}


Se puede ver que la unica funcion con complejidad no constante dentro 
del loop del algoritmo es la busqueda de una ficha para ubicar en la posicion i. 
Esa operacion recorre todas las fichas disponibles y ve cuales podrian encajar.
Dado que estoy en la posicion i, coloque i+1 fichas. Entonces recorrer
un arreglo de NxM - (i+1) fichas tiene orden lineal en la cantidad de fichas. 
Ahora el problema esta en ver cuantas veces se itera en el loop. 
Dado que cada vez que avanza es por que coloco una ficha y cada vez que retrocede
retiro una. La cantidad de fichas que se pueden probar en el paso i 
es la cantidad de fichas NxM -i, entonces se esta probando 
todas las permutaciones posibles. \\
NxM * NxM-1 * NxM -2,,,,,,NxM-NxM+1. \\
La cantidad de veces que voy a
probar una ficha en una posicion es NxM!. Como en cada 
paso busco entre a lo sumo NxM fichas, una para ubicar y calculo cuantas 
otras hay, tengo\\ NxM! * NxM ~ O(N*M+1!)).
\\
El orden de complejidad sera O(NxM+1!)



% Se presentara un pseudocodigo separado en 3 partes para poder ver mas claramente 
% las operacion y ver su correctitud.\\
% \begin{pseudocode}{Buscar}{i}
% \\
% \GLOBAL fichasDisponibles,N,M,tableroActual\\
% \\
% \COMMENT{\emph{fichasDisponibles} es una lista de fichas no ubicadas en el tablero }\\
% \COMMENT{\emph{tableroActual} es una lista que representa mi solucion actual }\\
% \COMMENT{\emph{mejorTablero} tablero hasta ahora con la menor cantidad de libres }\\
% \COMMENT{\emph{intentosPorPosicion} vector de \emph{NxM} con las fichas que quedan por probar en la pos i}\\
% \COMMENT{\emph{N, M} son las dimenciones del tablero }\\
% \COMMENT{\emph{izquierda,arriba, y fichaAux} son auxiliares para contener fichas, pueden ser un casillero libre }\\
% \\
% \\
% \IF i = N $*$ M \\
% \THEN
% \BEGIN
	
%     mejorSolucionLibres \GETS libresActual\\
%     mejorTablero \GETS tableroActual\\
%     \\      
%     \IF libresUsados <> \emptyset\\
%     \THEN
%     \BEGIN
%         posUltimoLibre\GETS \CALL{back}{libresUsados}\\
%         i \GETS posUltimoLibre - 1\\
%         \FOR j \GETS i \TO  N*M \DO
%         \BEGIN
%         	intentosPorPosicion[i] \GETS 0\\
%         	\CALL{devolverFichas}{tableroActual,i,fichasDisponibles}
%         \END
%         \\
%         \CALL{Buscar}{i}\\
%         \EXIT
%     \END
%     \ELSE
%     \BEGIN
%     	\COMMENT{Llegue a la solucion sin casilleros libres}\\
%     	\EXIT
%     \END
% \END
% \\
% \\
% \end{pseudocode}

% \begin{pseudocode}{Buscar}{i}
% \\
% \IF intentosPorPosicion[i] == 0 $ and $ i <> 0 
% \\
% \THEN 
% \BEGIN 
%     izquierda \GETS getIzquierda(tableroActual, i) \\
%     arriba \GETS getArriba(tableroActual, i)\\
%     intentosPorPosicion[i] \GETS dameFichaQueEncaje(izquierda, arriba, fichaAux)\\	     
%     \COMMENT{\emph{dameFichaQueEncaje} deja en fichaAux la ficha que matchea }\\
%     \COMMENT{y retorna la cantidad de posibilidades que hay}\\
%     \\   
% \END
% \\
% \ELSE
% \BEGIN
%         intentosPorPosicion[i] \GETS intentosPorPosicion[i] - 1 \\
%         \\
%         \IF  intentosPorPosicion[i] <= 1\\
%         \THEN
%         \BEGIN
% 	        \IF i = 0
% 	        \THEN 
% 	        \BEGIN
% 	        	\COMMENT{ No hay mas posibilidad de buscar caminos desde la posicion 0}\\
% 	        	\COMMENT{ En mejorTablero esta la mejor solucion que se encontro}\\
% 	        	\EXIT
% 	        \END
% 	        \\
% 	        \ELSE
% 	        \BEGIN
% 	        	\\
% 	            intentosPorPosicion[i] \GETS 0 \\
%                 \IF \CALL{estaVacio}{tableroActual,i - 1}
%                 \THEN
%                 \BEGIN
%                     \COMMENT{el algoritmo retrocede en una solucion}\\
%                     libresActual \GETS libresActual - 1\\                        
%                 \END
%                 \ELSE
%                 \BEGIN
%                     i \GETS i -1\\
%                     \CALL{Buscar}{i}\\
%                     \EXIT
%                 \END
% 	        \END
%         \END
%         \\
%         \ELSE
%         \BEGIN
%            	izquierda \GETS getIzquierda( tableroActual, i)\\
%             arriba \GETS getArriba(tableroActual, i)\\
%             dameFichaQueEncaje(izquierda, arriba, fichaAux)\\
%         \END
% \END

% \end{pseudocode}
% \\
% \\
% \begin{pseudocode}{Buscar}{i}
% \\
%         \IF \CALL{esLibre}{fichaAux}
%         \THEN
%         \BEGIN
%         \\
%             \IF libresActual + 1 >= mejorSolucionLibres
%             \THEN
%             \BEGIN
%             \COMMENT{hay otra mejor solucion, retrocedo}\\

%            		\IF \CALL{esLibre}{tablero,i-1}
%             	\THEN
%             	\BEGIN                
%                      libresActual \GETS libresActual - 1\\
%                      \CALL{remove}{casillerosLibres,i-1}\\
%                      \\
%              	\END
%              	\ELSE
%              	\BEGIN
% 					\CALL{push}{fichasDisponibles,tableroActual[i - 1]}\\
% 				\END
% 				\\
% 				intentosPorPosicion[i] \GETS 0\\
% 				i \GETS i - 1\\             	
%             \END
%             \ELSE
%             \BEGIN
%                 \CALL{posicionarFicha}{tableroActual, i, fichaAux}\\
%                 libresActual \GETS libresActual + 1\\
%                 \CALL{push}{casillerosLibres,i}\\
%                 i \GETS i + 1\\
%             \END
%         \END
%         \ELSE
%         \BEGIN
%             \CALL{posicionarFicha}{tableroActual, i, fichaAux}\\
%             i \GETS i + 1\\
%         \END\\
% 		\CALL{Buscar}{i}\\
% 		\EXIT
% \end{pseudocode}
% \\
% \\

% Como se puede ver en los 3 graficos en el primero
% se evalua el resultado de una solucion dado que se llego a la posicion $i = NxM$
% Pero como se esta buscando una solucion optima, ĺa unica posibilidad
% de terminar aqui la ejecucion es habiendo encontrado una solucion que deja 
% $\emph{libresUsados} = \emptyset$ . Osea que no se necesito dejar ningun casillero libre.
% En otro caso lo que se hace es registrar esa solucion como la nueva mejor solucion
% y se salta a hasta la posicion del ultimo casillero que se dejo libre. Cada
% vez que se deja un casillero libre se guarda registro de este para poder 
% volver luego de completada una solucion a retirarlo y tratar desde ese lugar
% de mejorar una solucion parcial. \\
% \\
% En el segundo grafico que sigue a continuacion se entra en todas
% las otras posiciones intermedias de una solucion. Como se puede ver se tiene un vector 
% que se llama \emph{intentosPorPosicion} esto es lo que garantiza que el algoritmo
% termine. Dado que cada vez que se retrocede, por que la solucion actual no lleva a una mejor 
% solucion que la mejor conocida, se intenta desde una posicion en la que ya se estuvo pero con
% otra ficha posible que habia para esa posicion. Se debe llevar de alguna manera registro
% que en esa posicion ya se rotaron todas las fichas posibles para esa posicion. 
% Cada vez que se avanza se toma una ficha para una posicion pero tambien la cantidad 
% de optiones entre las que se eligio esa ficha. Entonces cuando se quiere probar con otra 
% ficha y luego otra, se sabe que en esa posicion ya se rotaron todas las fichas posibles. Ahora 
% es momento de seguir retrocediendo, dado que en esa posicion no se pueden seguir intentando soluciones
% sin cambiar las fichas anteriores de mi solucion parcial.
% Cada vez que se busca una ficha para la posicion $i \in N x M $ se evalua si en ese 
% i ya se intentaron todas las posibilidades de camino. \\
% \\
% En el tercer recuadro, luego de ver que se puede seguir tratando desde la posicion $i$
% en la que se esta, se evalua si realmente la ficha que se desea colocar  en la solucion
% parcial actual me llevara a  una posible mejor solucion que la mejor conocida.
% Si es asi, se avanzara en una solucion desde la posicion $i+1$, pero si resulta
% que estoy por dejar un casillero libre y mi solucion parcial no permite mas casilleros
% libres, por que eso haria que sea igual a una que ya conozco con esa cantidad de casilleros libres,
% entonces debo evaluar otro camino. Por que este que estoy tomando evidentemente no mejorara
% el mejor camino que ya conozco.\\
% e\\
% Como observacion general se puede ver que en ningun momento el algoritmo mantiene 
% el $i$ entre 2 llamadas. Dentro de $Buscar(i)$ nunca se llama a $Buscar(j)$ con $i = j$. Siempre o se 
% avanza o se retrocede. Y cada avance o retroceso es trackeado por el vector $intentosPorPosicion$. Esto 
% hace que el algoritmo concluya dado que basicamente este vector es el arbol de posibilidades de solucion
% aplanado. Cada vez que se sube hacia la raiz(posiciones mas bajas del vector) se cortan soluciones por una rama
% del arbol. Cada vez que se avaanza o completan casilleros en el vector se esta avanzando hacia una posible 
% mejor solucion completa.

% El pseudocodigo que se presenta a continuacion, a diferencia 
% del presentado en la seccion de la demostracion se acerca mas  a
% lo que se puede ver en el codigo fuente de la implementacion.
% En este caso se opto por eliminar la recursion utilizando un loop
% principal y variables globales. Si bien esto en C++ no era necesario, la primera
% version del algoritmo fue en Python, y esto hizo que no sea posible desde un primer 
% momento contar con una version recursiva solida, pues el interprete de Python
% limita la cantidad de llamadas recursivas en una funcion. Por este motivo
% se paso de una version recursiva en Python a otra iterativa, para luego implementar 
% ese codico en C++ y tener un ejecutable que permita hacer mejores mediciones. Sin 
% las particularidades de un lenguaje no compilado.
% \\
% \\
% \\


% \hspace*{-1.5em}//cantidad de casilleros en blanco de la solucion actual\\
% $cantBlancos \leftarrow  0 $\\

% \hspace*{-1.5em}//cantidad de casilleros en blanco de la mejor solucion\\
% $mejorSolucionBlancos \leftarrow  N*M$\\

% \hspace*{-1.5em}//mejor solucion en fichas\\
% $mejorTablero \leftarrow  [ N*M : Fichas]$\\

% \hspace*{-1.5em}//solucion actual en fichas\\
% $tableroActual \leftarrow   [ N*M : Fichas]$\\

% \hspace*{-1.5em}//vector con la cantidad de fichas que puedo poner \\
% //en la posicion i para la solucion construida entre[0:i-1]\\
% $opcionesPorCasillero \leftarrow   [N*M: Int ]$\\

% \hspace*{-1.5em}//posiciones en las que deje un casillero en blanco en la solucion actual\\
% $casillerosBlancos \leftarrow []$\\

% \hspace*{-1.5em}fichas no utilizadas en la solucion actual\\
% $fichasDisponibles \leftarrow  [N*M : Fichas]$\\
% \begin{pseudo}
% 	\func{encontrarSolucion}{i}
% 	\tab//llegue al final de una solucion\\
% 	\tab\IF $i = NxM:$\\
% 	\tab\tab legue al final de una solucion\\
% 	\tab\tab mejorSolucionBlancos $\leftarrow$ cantBlancos\\
% 	\tab\tab mejorTablero $\leftarrow$ tableroActual\\

% 	\tab\tab devolver fichas a fichasDisponibles desde NxM-1 en el tablero actual \\
% 	\tab\tab hasta casillerosBlancos.pop() // hasta el ultimo casillero en blanco dejado en la \\
% 	\tab\tab //solucion actual\\
% 	\tab\tab //trato de mejorar esta solucion desde la posicion anterior al ultimo casillero\\
% 	\tab\tab //en blanco a ver si puedo no dejar blancos al cambiar la ficha \\
% 	\tab\tab // posUltimoBlanco -1  por otra\\
% 	\tab\tab encontrarSolucion(posUltimoBlanco -1 ) \\
% 	\tab\\	
% 	\tab\IF opcionesPorCasillero[i] = 0:\\
% 	\tab\tab //cuando el algoritmo avanza en una solucion\\
% 	\tab\tab //busco la ficha a izquiera de la pos actual,  blanco sino \\
% 	\tab\tab izq $\leftarrow$ 	getIzquierda(i)\\
% 	\tab\tab //busco la ficha superior a la actual, blanco sino\\
% 	\tab\tab arriba $\leftarrow$  getArriba(i)\\
% 	\tab\tab //busco entre las fichas  en fichas disponibles una ficha que encaje\\
% 	\tab\tab //para izq y arriba, aca si son bordes se ignora ese lado.\\
% 	\tab\tab //cabe mencionar que fichasDisponibles funciona como una cola para no tomar \\
% 	\tab\tab //2 iteraciones la misma ficha como camino posible en un punto dado\\
% 	\tab\tab (ficha,opciones) $\leftarrow$ getFicha(izq,arriba)\\
% 	\tab\ELSE\\
% 	\tab\tab//estoy retrocediendo, este casillero ya lo complete pero la ficha \\
% 	\tab\tab//que eleji no me lleva a una solucion mejor, tomo otra entre las otras opciones \\
% 	\tab\tab//que tenia, siempre me manejo en orden circular para tomar la siguiente opcion\\
% 	\tab\tab//para no repetir la ficha\\
% 	\tab\tab opcionesPorCasillero[i] $\leftarrow$ opcionesPorCasillero[i] - 1\\
% 	\tab\tab \IF opcionesPorCasillero[i] = 0:\\
% 	\tab\tab\tab//no puedo cambiar mas fichas en esta posicion\\
% 	\tab\tab\tab\IF i = 0 \\
% 	\tab\tab\tab\tab Fin //no hay mas soluciones me quede sin permutaciones\\
% 	\tab\tab\tab //tengo que seguir retrocediendo \\
% 	\tab\tab\tab //no hay mas opciones para i con ese i-1 asi que tengo que cambiarlo\\
% 	\tab\tab\tab\IF esBlanco(tableroActual[i] ):\\
% 	\tab\tab\tab\tab //resulta que la posicion i era blanco \\
% 	\tab\tab\tab\tab //asi que tengo que remover ese blanco de mis estructuras\\
% 	\tab\tab\tab\tab cantBlancos $\leftarrow$ cantBlancos - 1 		\\
% 	\tab\tab\tab\tab remover(casillerosBlancos, i)\\
% 	\tab\tab\tab\ELSE\\
% 	\tab\tab\tab\tab //si habia una ficha en la posicion i tengo qeu devolverla al set de \\
% 	\tab\tab\tab\tab //fichas disponibles \\
% 	\tab\tab\tab\tab devolverFicha(tableroActual,fichasDisponibles,i)\\
% 	\tab\tab\tab //ahora trato de tomar otro camino partiendo desde la posicion \\
% 	\tab\tab\tab //i-1 que sea mejor que la mejor conocida\\
% 	\tab\tab\tab entoncontrarSolucion(i-1) \\
% 	\tab\tab \ELSE \\
% 	\tab\tab\tab //sigo intentando en la pos i con otras fichas, resulta que retrocedi \\
% 	\tab\tab\tab //pero todabia en la posicion i tengo opciones para intercambiar fichas, \\
% 	\tab\tab\tab //osea probar otros caminos partiendo desde i pero con otras fichas\\
% 	\tab\tab\tab //busco otra ficha para completar i  y devuelvo la que estaba\\
% 	\tab\tab\tab izq $\leftarrow$ 	getIzquierda(i)\\
% 	\tab\tab\tab arriba $\leftarrow$  getArriba(i)\\
% 	\tab\tab\tab (ficha,opciones) $\leftarrow$ getFicha(izq,arriba)\\
% 	\tab\tab\tab //no actualizo las opciones por que estoy probando con otra \\
% 	\tab\tab\tab //ficha desde el mismo lugar\\
% 	\tab\tab\tab opciones $\leftarrow$ opcionesPorCasillero[i]\\
% 	\tab\tab\tab devolverFicha(tableroActual,fichasDisponibles,i)\\
% 	\tab\tab\\ 	 
% 	\tab\IF esBlanco(ficha) :\\
% 	\tab\tab //la ficha que eleji para poner en i es un blanco\\
% 	\tab\tab\IF cantBlancos + 1 =  mejorSolucionBlancos:\\
% 	\tab\tab\tab// esta solucion ya no me sirve, por que no mejoro una existente.\\
% 	\tab\tab\tab opcionesPorCasillero[i] $\leftarrow$ 0\\
% 	\tab\tab\tab encontrarSolucion(i-1)\\
% 	\tab\tab\ELSE\\
% 	\tab\tab\tab //toy con una solucion todabia mejor a la mejor conocida\\
% 	\tab\tab\tab cantBlancos $\leftarrow$  cantBlancos +1\\
% 	\tab\tab\tab apendar a  casillerosBlancos  la posicion  i\\
% 	\tab\tab\tab opcionesPorCasillero[i] $\leftarrow$ 1\\
% 	\tab\tab\tab encontrarSolucion(i+1)\\
% 	\tab\ELSE
% 	\tab\tab //eleji una ficha para la posicion actual y la cantidad de veces que \\
% 	\tab\tab //puedo cambiar fichas en i, dada la solucion desde [0:i] es el valor de la \\
% 	\tab\tab //variable opciones\\
% 	\tab\tab posicionarFicha(tableroActual,i, ficha)\\
% 	\tab\tab opcionesPorCasillero[i] $\leftarrow$ opciones\\
% 	\tab\tab //sigo completando fichas desde i+1\\
% 	\tab\tab encontrarSolucion(i+1)\\
% 	\end{pseudo}


% Tener la posibilidad de dejar casilleros en blanco en la solucion hace 
% que en la primer solucion posible se reduzcan los intentos. 
% El algoritmo ira avanzando $(NxM)$ casilleros buscando una ficha que encaje
% con las anteriores ($NxM-i$ siendo $i$ la posicion actual). En caso de utilizarse
% una estructura de arbol que indexce por coordenada izquierda y superior de la ficha 
% se puede mejorar esta complejidad de busqueda entre las fichas disponibles.
% Osea que en la primer solucion tenemos en el peor de los casos. 
% %$\sum\limits$$_{j=i}^n d_{j}$
% $\sum\limits$$_{i=1}^{N*M} $$N*M-i$ Luego para la lista $casillerosLibres$, se 
% ira retirando cada uno de los casilleros que se dejaron en blanco, desde atras hacia adelante(primeros
% puestos) y se intentara completar la solucion.
% Ahora como no se pueden poner mas casilleros en blanco por que estamos tratando 
% de mejorar una solucion de K casilles libres con una nueva de k-1. Cada 
% vez que avancemos necesitaremos tener al menos una ficha para colocar. En otro caso se debera retroceder.
% Este es el momento donde empieza la fuerza bruta para completar una solucion parcial.
% Para cada posicion $i$ tendre a lo sumo $NxM-i$ posibles fichas en el peor  los casos. 
% El orden de complejidad en esta etapa de \emph{mejora} de una solucion parcial es 
% factorial teniendo para la posicion $i$ un orden $i!$

% Si $S$ es la lista de casilleros libres que se dejaron, entonces el proceso de mejora 
% para poder retirar todos los casilleros que se dejaron en blanco en la primer solucion. 
% Tiene como peor caso aquel en el que se podran remover todos. 
% En este caso para cada $s \in S$ se tendra $s!$. La complejidad en definitiva 
% sera la de la primera solucion mas la de las $n$ mejoras(con $n$ la longitud de $S$) que se hagan en cuanto a quita de casilleros
% libres. \\
% \\
% $\sum\limits$$_{i=1}^{N*M} $$N*M-i$ $+$ $\sum\limits$$_{s \in S} $$s!$. \\
% \\
% Esto es un orden de complejidad  por lejos mayor que el real del algoritmo. Dado que se esta suponiendo que  para cada 
% casillero que se retira, y en el intento de una nueva solucion con $n-1$ casilleros libres, 
% se intentara con todas las permutacines posibles. Esto no es asi dado que 
% en el primer intento de colocar un comodin la solucion sera descartada, cosa que reducira
% en mucho la cantidad de permutaciones intentadas.
